class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size(); // 0-不持有 1-持有
        vector<vector<int>> rec(n, vector<int>(2));
        rec[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            rec[i][0] = max(rec[i - 1][0], rec[i - 1][1] + prices[i] - fee);
            rec[i][1] = max(rec[i - 1][0] - prices[i], rec[i - 1][1]);
        }
        return max(rec[n - 1][0], rec[n - 1][1]);
    }
};

// 简化变量
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size(); // 0-不持有 1-持有
        int sell = 0;
        int buy = -prices[0];
        for (int i = 1; i < n; ++i) {
            sell = max(sell, buy + prices[i] - fee);
            buy = max(sell - prices[i], buy);
        }
        return max(buy, sell);
    }
};

// 贪心
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int buy =INT_MAX;
        int profit = 0;
        for(int i = 0; i < prices.size(); i++){
            buy = min(prices[i] + fee, buy);
            if(prices[i] > buy){
                //这里不一定要卖，只不过先存起来，下一次比较，有更低的就更新
                profit += prices[i] - buy;
                buy = prices[i];
            }
        }
        return profit;
    }
};

// 有了手续费所以不能这么写，不知道买卖次数
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> res(n, 0);
        for (int i = 1; i < n; ++i) {
            res[i] = max(res[i - 1], res[i - 1] + prices[i] - prices[i - 1]);
        }
        return res.back();
    }
};